Teorio de komputado

La teorio de komputado estas la branĉo de komputado, kiu traktas, ĉu kaj kiel komputaj taskoj povas esti kompetente solvitaj per komputilo. La kampo estas dividita en du ĉefaj branĉoj: teorio de komputebleco kaj komplikteorio, sed ambaŭ branĉoj formaligas modelojn de komputado.

Por plenumi rigoran studon de komputado, komputilo-sciencistoj laboras kun matematikaj abstraktaĵoj de komputiloj nomataj kiel modelo de komputado. Estas kelkaj formulaĵoj uzataj, sed la plej kutime ekzamenata estas la maŝino de Turing. Maŝino de Turing povas esti konceptita kiel labortabla persona komputilo kun malfinia memora kapacito, kvankam ĝi povas atingi tiun memoron nur en malgrandaj diskretaj buloj. Komputikistoj studas la maŝinon de Turing ĉar ĝi estas simple formulebla, povas esti analizita kaj kutime eblas pruvi la rezultojn, kaj ĉar ĝi prezentas tion kion multaj konsideras kiel la plej pova ebla "modera" modelo de komputado. Dum la malfinia memora kapacito povus esti konsiderata nefizika atributo, por ajna problemo reale solvata per maŝino de Turing la memoro uzata ĉiam estas finia, do ajna problemo, kiu povas esti solvita per maŝino de Turing povis esti solvita per kutima reala komputilo, kiu havas sufiĉan memoron.